lcmefandomcom_ru-20200213-history
Массивы
Определение Массив - тип данных, имеющий сигнатуру 'a\ array , являющийся контейнером и содержащий так называемые mutable-значения, то есть его содержимое можно редактировать "на месте" ("in-place"), не создавая новый экземпляр, как это происходит со списками. Создаются массивы при помощи функции int \to\ 'a \to\ 'a\ array или её синонима Array.create , где первым аргументом является длина массива, а вторым - инициализирующий элемент, которому будут равны все элементы массива после его создания. Доступ к элементу массива осуществляется либо при помощи функции 'a\ array \to\ int \to\ 'a , либо с помощью синтаксиса a.(i), где a - название массива, i - индекс (номер) требуемого элемента. Для записи в массив существует функция 'a\ array \to\ int \to\ 'a \to\ unit , либо синтаксис a.(i) <- x, где x - новое значение для ячейки i массива a. Главное отличие массивов от списков состоит в том, что списки легко изменяют свой размер, но с трудом индексируются; с массивами же всё наоборот. Для списка операция добавления элемента ( :: ) является базовой и работает за O(1) , но доступ к элементу под номером n происходит за O(n) ; в массиве же доступ к элементу является базовой операцией и работает за O(1) , а изменение размера - по крайней мере за O(n) , где n - это новый размер. Классические массивы - это просто кусок памяти, длина которого - это произведение размера одного элемента массива и количества элементов в нём. В OCaml'е на них ещё навешен счётчик, их длина, с тем чтобы функция Array.length работала за константное время. Есть ещё другая религия, пришедшая из Си, где конец массива помечается специальным маркером, и функция вычисления длины просто шагает вперёд по массиву в его поисках. Как нетрудно заметить, ошибка "Array index out of bounds" там гораздо более непредсказуемая, чем в OCaml'е :) Дополнительные функции Для удобства в модуле Array есть некоторые дополнительные функции для работы с массивами. В первую очередь стоит упомянуть функцию 'a\ array \to\ int , возвращающую длину данного массива. Кроме того, следует отметить функцию int \to\ (int \to\ 'a) \to\ 'a\ array , создающую массив по функции от индекса; например, с её помощью очень легко создать массив-вектор: let vect = Array.init 10 (fun i -> i) Кроме того, есть стандартные функции ('a \to\ 'b) \to\ 'a\ array \to\ 'b\ array и ('a \to\ unit) \to\ 'a\ array \to\ unit , обладающие той же функциональностью, что и их аналоги из модуля List. Однако также имеются их продвинутые аналоги: (int \to\ 'a \to\ 'b) \to\ 'a\ array \to\ 'b\ array и (int \to\ 'a \to\ unit) \to\ 'a\ array \to\ unit , отличающиеся от своих собратьев тем, что функция, которую они берут в качестве первого параметра, должна быть от двух аргументов: от индекса элемента в массиве и от самого элемента. Цикл for При работе с массивами очень удобно использовать циклы. В конце концов, и то, и другое было придумано императивщиками :) Итак, встречайте цикл for: for var = low to high do (* code here *) done Здесь var - счётчик цикла, low - начальное значение, high - конечное. Поясню. Код внутри цикла выполнится high - low + 1 раз, если high \geq low и 0 в противном случае. На каждой итерации для кода внутри цикла будет доступно текущее значение счётчика, равное low + i , где i - количество уже совершённых итераций. Пример: let print_array a = for i = 0 to pred (Array.length a) do print_endline a.(i) done Итак, количество итераций цикла for всегда должно быть известно в момент его начала. Так бывает часто, но не всегда. И вот как раз для случаев "не всегда" был придуман цикл while. Цикл while while cond do (* code here *) done Здесь cond - это некоторое значение типа bool, которое вычисляется перед каждой итерацией цикла и определяет, будет ли выполнена эта итерация. Пример: while true do () done Эта программа умеет очень классно виснуть :) Наивный поиск Определение: наивный алгоритм - самый очевидный (и , как правило, самый тупой) алгоритм из всех, что можно придумать. Таким образом, наивный поиск элемента в массиве - это перебор всех элементов в надежде обнаружить требуемый. let find x a = let len = Array.length a in let rec find_aux i = if i = len then None else if a.(i) = x then Some i else find_aux (succ i) in find_aux 0 Очевидно, что сей гениальный алгоритм обладает несомненным достоинством - он работает правильно на любом массиве. Впрочем, время его работы сводит на на это потрясающее достоинство: он работает прямо пропорционально длине массива, то есть O(n) . Очевидно, что это не есть хорошо. Нужен был прорыв... и прорыв произошёл. Двоичный поиск Пусть дан отсортированный массив, причём на его элементах определена операция сравнения. Рассмотрим середину массива и сравним её с искомым элементом. Очевидно, что если она больше, то искомый элемент находится левее её, если меньше - то правее, если они совпали - задача решена, если указатели столкнулись, а элемента нету - ну что ж, жаль. Повторить рекурсивно... let qfind x a = let rec qfind_aux l r = let i = (l + r) / 2 in if a.(i) = x then Some i else if i = l then None else if a.(i) > x then qfind_aux l i else qfind_aux i r in qfind_aux 0 (Array.length a) Понятно, что на каждой итерации алгоритма область поиска сужается вдвое, следовательно, количество операций, которые алгоритму необходимо выполнить - это не более чем то, сколько раз массив можно ещё делить пополам, то есть двоичный логарифм от его длины, поэтому сложность алгоритма - O(logn) . Кстати, следует заметить, что массив - это функция int -> int, потому что... Обратная функция Двоичный поиск имеет ещё одно, неожиданное, применение: вычисление значения функции, обратной к монотонной. Рассмотрим случай монотонно возрастающей функции; случай монотонно убывающей очевидно вытекает из него. Алгоритм используется почти тот же самый, только поиск производится не по массиву, а по типу float. let inverse f x = let rec estimate l r = let i = (l +. r) /. 2. in let fi = f i in if (r -. l <= 0.000001) || (fi = x) then i else if fi < x then estimate i r else estimate l i in estimate 0. x Эта функция позволяет вычислить, например, корень любой натуральной степени из любого положительного числа. Несложные изменения позволяют приспособить её под вычисление любых других обратных монотонных функций. Категория:Программирование